package com.shm.leetcode;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

/**
 * 846. 一手顺子
 * Alice 手中有一把牌，她想要重新排列这些牌，分成若干组，使每一组的牌数都是 groupSize ，并且由 groupSize 张连续的牌组成。
 *
 * 给你一个整数数组 hand 其中 hand[i] 是写在第 i 张牌，和一个整数 groupSize 。如果她可能重新排列这些牌，返回 true ；否则，返回 false 。
 *
 *
 *
 * 示例 1：
 *
 * 输入：hand = [1,2,3,6,2,3,4,7,8], groupSize = 3
 * 输出：true
 * 解释：Alice 手中的牌可以被重新排列为 [1,2,3]，[2,3,4]，[6,7,8]。
 * 示例 2：
 *
 * 输入：hand = [1,2,3,4,5], groupSize = 4
 * 输出：false
 * 解释：Alice 手中的牌无法被重新排列成几个大小为 4 的组。
 *
 *
 * 提示：
 *
 * 1 <= hand.length <= 104
 * 0 <= hand[i] <= 109
 * 1 <= groupSize <= hand.length
 *
 *
 * 注意：此题目与 1296 重复：https://leetcode-cn.com/problems/divide-array-in-sets-of-k-consecutive-numbers/
 * @author SHM
 */
public class IsNStraightHand {
    /**
     * 方法一：贪心
     * 题目要求将数组 \textit{hand}hand 中的牌分组使得每组的大小是 \textit{groupSize}groupSize。假设数组 \textit{hand}hand 的长度是 nn，只有当 n \bmod \textit{groupSize} = 0nmodgroupSize=0 时才可能完成分组，因此如果 n \bmod \textit{groupSize} \ne 0nmodgroupSize
     * 
     * ​
     *  =0 则直接返回 \text{false}false。
     *
     * 当 n \bmod \textit{groupSize} = 0nmodgroupSize=0 时，可以将数组 \textit{hand}hand 中的牌分组使得每组的大小是 \textit{groupSize}groupSize，此时需要判断是否存在一种分组方式使得同一组的牌都是连续的。
     *
     * 由于每张牌都必须被分到某个组，因此可以使用贪心的策略。假设尚未分组的牌中，最小的数字是 xx，则如果存在符合要求的分组方式，xx 一定是某个组中的最小数字（否则 xx 不属于任何一个组，不符合每张牌都必须被分到某个组），该组的数字范围是 [x, x + \textit{groupSize} - 1][x,x+groupSize−1]。在将 xx 到 x + \textit{groupSize} - 1x+groupSize−1 的 \textit{groupSize}groupSize 张牌分成一个组之后，继续使用贪心的策略对剩下的牌分组，直到所有的牌分组结束或者无法完成分组。如果在分组过程中发现从最小数字开始的连续 \textit{groupSize}groupSize 个数字中有不存在的数字，则无法完成分组。
     *
     * 首先对数组 \textit{hand}hand 排序，并使用哈希表记录数组 \textit{hand}hand 中每个元素的出现次数，然后遍历数组 \textit{hand}hand，使用基于上述贪心策略的做法判断是否可以完成分组。贪心策略的具体做法如下：
     *
     * 将当前元素记为 xx，如果 xx 不在哈希表中则跳过，如果 xx 在哈希表中，则 xx 是某个组中的最小数字（因为数组 \textit{hand}hand 有序，当遍历到 xx 时，xx 一定是所有尚未分组的元素中的最小数字），该组的数字范围是 [x, x + \textit{groupSize} - 1][x,x+groupSize−1]；
     *
     * 如果可以完成分组，则 xx 到 x + \textit{groupSize} - 1x+groupSize−1 的每个整数在哈希表中记录的出现次数都至少为 11，如果遇到某个整数的出现次数为 00 则无法完成分组，返回 \text{false}false；
     *
     * 将 xx 到 x + \textit{groupSize} - 1x+groupSize−1 的每个整数在哈希表中记录的出现次数减 11，如果出现次数减为 00 则从哈希表中移除该整数；
     *
     * 对于其余元素，重复上述操作，直到遍历结束。
     *
     * 遍历结束之后，如果没有出现无法完成分组的情况，返回 \text{true}true。
     * 复杂度分析
     *
     * 时间复杂度：O(n \log n)O(nlogn)，其中 nn 是数组 \textit{hand}hand 的长度。对数组 \textit{hand}hand 排序需要 O(n \log n)O(nlogn) 的时间，排序之后遍历数组 \textit{hand}hand 两次，每次遍历过程中，每个元素的处理时间都是 O(1)O(1)，因此每次遍历的时间复杂度都是 O(n)O(n)，总时间复杂度是 O(n \log n)O(nlogn)。
     *
     * 空间复杂度：O(n)O(n)，其中 nn 是数组 \textit{hand}hand 的长度。空间复杂度主要取决于哈希表，哈希表中最多存储 nn 个元素。
     *
     * 作者：LeetCode-Solution
     * 链接：https://leetcode-cn.com/problems/hand-of-straights/solution/yi-shou-shun-zi-by-leetcode-solution-4lwn/
     * @param hand
     * @param groupSize
     * @return
     */
    public boolean isNStraightHand(int[] hand, int groupSize) {
        int n = hand.length;
        if (n%groupSize!=0){
            return false;
        }
        Arrays.sort(hand);
        Map<Integer,Integer> map = new HashMap<>();
        for (int i : hand) {
            map.put(i,map.getOrDefault(i,0)+1);
        }
        for (int i : hand) {
            if (!map.containsKey(i)){
                continue;
            }
            for (int j = 0; j < groupSize; j++) {
                int num = i+j;
                if (!map.containsKey(num)){
                    return false;
                }
                map.put(num,map.get(num)-1);
                if (map.get(num)==0){
                    map.remove(num);
                }
            }
        }
        return true;
    }
}
